package com.seven.leetcode.problems;

import java.util.Arrays;
import java.util.IntSummaryStatistics;

/**
 * 面试题 17.21. 直方图的水量
 * https://leetcode-cn.com/problems/volume-of-histogram-lcci/
 * 级别：Hard
 * <p>
 * 给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。
 * 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出: 6
 * <p>
 * 输入: [4,2,3]
 * 输出: 1
 *
 * @author : wenguang
 * @date : 2021/4/02 10:42
 */
public class VolumeOfHistogramLcci {

    public static void main(String[] args) {
//        int[] heights = new int[]{0,1,0,2,1,0,1,3,2,1,2,1};
        int[] heights = new int[]{4, 2, 3};
        System.out.println("in: \nheights:" + Arrays.toString(heights));
        int result = trap3(heights);
        System.out.println("out: " + result);
    }

    public static int trap3(int[] height) {
        if (null == height || height.length <= 2) {
            return 0;
        }

        int length = height.length;
        int max = height[0];
        for (int i = 1; i < length; i++) {
            if (height[i] > max) {
                max = height[i];
            }
        }

        int allSum = 0;
        int i = 0;
        while (height[i] < max) {
            if (height[i] > height[i + 1]) {
                allSum += (height[i] - height[i + 1]);
                height[i + 1] = height[i];
            }

            i++;
        }

        int j = length - 1;
        while (height[j] < max || j > i) {
            if (height[j] > height[j - 1]) {
                allSum += (height[j] - height[j - 1]);
                height[j - 1] = height[j];
            }
            j--;
        }

        return allSum;
    }

    public static int trap2(int[] height) {
        if (null == height || height.length <= 2) {
            return 0;
        }

        IntSummaryStatistics statistics = Arrays.stream(height)
            .summaryStatistics();

        int max = statistics.getMax();
        int allSum = 0;
        int i = 0;
        while (height[i] < max) {
            if (height[i] > height[i + 1]) {
                height[i + 1] = height[i];
            }
            allSum += height[i];
            i++;
        }

        int j = height.length - 1;
        while (height[j] < max) {
            if (height[j] > height[j - 1]) {
                height[j - 1] = height[j];
            }
            allSum += height[j];
            j--;
        }

        allSum += (j + 1 - i) * max;
        return allSum - Math.toIntExact(statistics.getSum());
    }

    public static int trap1(int[] height) {
        if (null == height || height.length <= 2) {
            return 0;
        }

        IntSummaryStatistics statistics = Arrays.stream(height)
            .summaryStatistics();

        int max = statistics.getMax();
        int i = 0;
        if (height[i] != max) {
            while (true) {
                i++;
                if (height[i] < max) {
                    if (height[i - 1] > height[i]) {
                        height[i] = height[i - 1];
                    }
                } else {
                    break;
                }
            }
        }

        int j = height.length - 1;
        if (height[j] != max) {
            while (true) {
                j--;
                if (height[j] < max) {
                    if (height[j + 1] > height[j]) {
                        height[j] = height[j + 1];
                    }
                } else {
                    break;
                }
            }
        }

        if (i < j) {
            Arrays.fill(height, i, j, max);
        }

        int sum = Arrays.stream(height)
            .sum();

        return sum - Math.toIntExact(statistics.getSum());
    }
}
